package 中等.哈希表;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。
 * 我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，
 * 使得连接的结果和按升序排序后的原数组相同。
 * 返回数组能分成的最多块数量。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/max-chunks-to-make-sorted
 */
public class 最多能完成排序的块_769 {

    public static void main(String[] args) {

        System.out.println(maxChunksToSorted(new int[]{4, 3, 2, 1, 0}));

    }

    /**
     * 排序+哈希表
     * 同时遍历原始数组和排序数组，分别用两个哈希表记录，用于记录不能互相抵消的元素
     * 如果两个哈希表为空，则说明之前的一段是一个最短分区，每次都是最短分区，分区
     * 数量是最多的
     */
    public static int maxChunksToSorted(int[] arr) {
        int count = 0;
        int[] sortArr = new int[arr.length];
        System.arraycopy(arr, 0, sortArr, 0, arr.length);
        Arrays.sort(sortArr);
        Set<Integer> arrSet = new HashSet<>();
        Set<Integer> sortArrSet = new HashSet<>();

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == sortArr[i]) {
                if (arrSet.size() == 0 && sortArrSet.size() == 0) {
                    count++;
                }
            } else {

                if (sortArrSet.contains(arr[i])) {
                    sortArrSet.remove(arr[i]);
                } else {
                    arrSet.add(arr[i]);
                }

                if (arrSet.contains(sortArr[i])) {
                    arrSet.remove(sortArr[i]);
                } else {
                    sortArrSet.add(sortArr[i]);
                }

                if (arrSet.size() == 0 && sortArrSet.size() == 0) {
                    count++;
                }
            }
        }

        return count;
    }

    // TODO 贪心

}
